package com.hs;

/**
 * @Author: hs
 * @Description:
 * @Date: Create in 14:53 2019/3/7
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {12, 1, 3, 7, 34, 56, 34, 12,  -3,3,-23,76, 9};
        mergeSort(arr);
        QuickSort.printArr(arr);
    }

    public static void mergeSort(int[] arr) {
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
    }

    /**
     * @param arr 待排序的数组
     * @param left 最初的左边的下标 0
     * @param right 最初的右边下标 length - 1
     * @param temp 就是临时数组 , 事先就开辟好的，大小和 arr 一样.
     */
    private static void mergeSort(int[] arr,int left,int right,int[] temp) {
        if (left<right){
            int mid = (left + right) / 2;
            // 递归将左边的数据做成有序列表
            mergeSort(arr, left, mid, temp);
            //递归将右边的数据做成有序列表
            mergeSort(arr, mid + 1, right, temp) ;
            // merge 是合并的操作
            merge(arr, left, mid, right, temp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // i 就是左边指针[索引]
        int i = left;
        //j 就是右边的指针
        int j = mid + 1;
        // t 是 temp 数组的索引
        int t = 0;
        while (i <= mid && j <= right) {
            // 如果是当前的左边的有序列表的值小于当前的右边有序列表的值
            // 就把这个值拷贝到 temp 数组
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else { // 如果是当前的右边的有序列表的值小于当前的左边有序列表的值，就把这个值拷贝到 temp
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }
        //如果左边有序列表还有剩余数据，就依次拷贝到 temp 数组
        while (i <= mid) {
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        //如果右边有序列表还有剩余数据，就依次拷贝到 temp 数组
        while (j <= right) {
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
        // 下面代码是完成将本次的 temp 的数据拷贝到 arr 中
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }

}
